package 二分法;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 二分法  ,主要是找到左边界和右边界
 * @date 2022/10/14 11:25
 */
public class Demo34 {

    public int[] searchRange(int[] nums, int target) {
        if(nums.length<1){
            return new int[]{-1,-1};
        }
        if(nums.length==1){
            if(nums[0]==target){
                return new int[]{0,0};
            }
        }
        int[] ints=new int[2];
        //找左边界
        ints[0]=binarySearch(nums,target,true);
        //找右边界
        ints[1]=binarySearch(nums,target,false);
        return ints;
    }

    private int binarySearch(int[] nums, int target, boolean b) {
        //左闭右闭,res记录边界位置，找不到就返回-1
        int left=0,right=nums.length-1,res=-1;
        //左闭右闭，所以是小于等于
        while (left<=right){
            //防止越界
            int mid=left+(right-left)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else {
                //证明找到了目标值开始，记录位置，同时开始找左边的目标值以及右边的目标值
                res=mid;
                if (b){
                    right=mid-1;
                }else {
                    left=mid+1;
                }
            }
        }
        return res;
    }
}
